package com.al.study.record.sort;

/**
 * Created by yuxi on 2017/8/31.
 */
public class SelectSort {
    public static void main(String[] args) {
        int[] arr = {-2, 1, 33, 4, 5, 0, 0, -1, 45, 908, 3};
        int[] sortList = selectSort(arr);
        for (int i : sortList) {
            System.out.print(i + "  ");
        }
        System.out.println();
        int[] sortListSample = selectSortSample(arr);
        for (int i : sortListSample) {
            System.out.print(i + "  ");
        }
    }

    /**
     * 简单实现，两两比较
     *
     * @param arr
     * @return
     */
    private static int[] selectSortSample(int[] arr) {
        if (arr.length < 0) {
            return null;
        }
        int N = arr.length;
        int j, i;
        for (i = 0; i < N; i++) {
            for (j = i + 1; j < N; j++) {
                //在这个位置会有很多次的交换，但是这些应该都是不必要，
                // 我们只需要把最小的角标标识出来移动一次就OK了
                if (arr[j] > arr[j]) {
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
        }
        return arr;
    }

    /**
     * 比较排序
     *
     * @param arr
     * @return
     */
    private static int[] selectSort(int[] arr) {
        if (arr.length < 0) {
            return null;
        }
        int N = arr.length;
        int j, i;
        for (i = 0; i < N; i++) {
            // 标记最小的角标
            int min = i;
            for (j = i + 1; j < N; j++) {
                if (arr[min] > arr[j]) {
                    min = j;
                }
            }
            // switch 把最小的元素和当前的元素交换
            /** 注意是arr[i]和arr[min]交换**/
            if (i != min) {
                int temp = arr[i];
                arr[i] = arr[min];
                arr[min] = temp;
            }
        }
        return arr;
    }
}
